/*Copyright (c) Microsoft Open Technologies, Inc.  All rights reserved.
Microsoft Open Technologies would like to thank its contributors, a list
of whom are at https://interview.codeplex.com/team/views.

Licensed under the Apache License, Version 2.0 (the "License"); you
may not use this file except in compliance with the License. You may
obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied. See the License for the specific language governing permissions
and limitations under the License.*/

/*
Problem:
    There is an integer array A, the size is N, all the item within it are between 1 and N,
    some integers eixst more than once while some doesn't exist.

    Now, let's desgin an algorithm to find out all items (1~N) which don't exist in the array and
    all items (1~N) which exist more than once.

Version 2:
    Change the requirement to print all the items with its occurrence count.
*/

#include <iostream>
#include <array>
using namespace std;

template<int N>
class array_stat {
public:
    array_stat(const array<int, N>& arr) : m_arr(arr) {
    }

    void operator()() {
        for (int i=1; i<=N; i++) {
            process(i);
        }

        for (int i=0; i<N; i++) {
            cout << i+1 << " exists " << m_arr[i] + N << " times." << endl;
        }
    }
private:
    array<int, N> m_arr;

    void process(int i) {
        // If the value is greater than 0, the item hasn't been processed.
        if (m_arr[i-1] > 0) {
            int cur = m_arr[i-1];

            // Set initial occurrence count to -N
            m_arr[i-1] = -N;
            process(cur);
        }
        else {
            // Otherwise, just increase its occurrence.
            m_arr[i-1]++;
        }
    }
};

int main() {
    array<int, 10> arr = {2, 1, 4, 3, 5, 6, 5, 6, 5, 6};
    array_stat<10> stat(arr);
    stat();
    return 0;
}